package com.future;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * Description:
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 *
 * @author weiruibai.vendor
 * Date: 2022/2/19 08:51
 */
public class Solution_levelOrder_102 {

    public static void main(String[] args) {
        TreeNode head = new TreeNode(3);
        head.left = new TreeNode(9);
        head.right = new TreeNode(20);
        head.right.left = new TreeNode(15);
        head.right.right = new TreeNode(7);
        levelOrder(head);
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        TreeNode nextNode = root.left != null ? root.left : root.right;
        List<Integer> tmpAns = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (nextNode == poll) {
                ans.add(tmpAns);
                nextNode = poll.left != null ? poll.left : poll.right;
                tmpAns = new ArrayList<>();
            }
            if (nextNode == null) {
                // 这种情况出现在上面的左右子数都为空的场景，给个机会赋值
                nextNode = poll.left != null ? poll.left : poll.right;
            }
            tmpAns.add(poll.val);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        // 最后一次需要手动添加
        ans.add(tmpAns);
        return ans;
    }

    public static List<List<Integer>> levelOrder_v2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Set<TreeNode> set = new HashSet<>();
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode nextNode = root.left;
        set.add(nextNode);
        List<Integer> tmpAns = new ArrayList<>();
        while (!queue.isEmpty() && queue.peek() != null) {
            TreeNode curNode = queue.poll();
            if (set.contains(curNode)) {
                ans.add(tmpAns);
                tmpAns = new ArrayList<>();
                set.clear();
            }
            tmpAns.add(curNode.val);
            if (curNode.left != null) {
                queue.add(curNode.left);
                set.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
                set.add(curNode.right);
            }
        }
        // 最后一行，需要手动添加
        ans.add(tmpAns);
        return ans;
    }
/*
    private List<List<Integer>> process(Queue<TreeNode> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }


    }*/

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left.val +
                    ", right=" + right.val +
                    '}';
        }
    }
}

